0% completed
Exponential Time Complexity
Key Characteristics
In an algorithm with
- Time Complexity: The number of operations doubles with each additional element in the input.
- Space Complexity: The memory usage also doubles, as each recursive call requires additional stack frames.
Code Example: Find All Subsets of a Given List
Below is a Java example that finds all subsets of a given list using recursion:
- Explanation:
- The
mainmethod starts the recursive process. - The helper function
findSubsetsgoes through each element in the list. - At every call, the function makes two recursive calls: one that skips the current element and one that adds it.
- When the index reaches the size of the list, the current list is added to the results.
- The
Complexity Analysis
Time Complexity
To estimate the time taken, we can use a recurrence relation.
Step 1: Define the Recurrence Relation
- Let T(n) be the time to compute all subsets of a list with n elements.
- At each step, the function makes two recursive calls.
T(n) = 2 * T(n - 1) + O(1)
Step 2: Expand the Recurrence Relation
-
When we expand T(n), we see that the number of calls doubles at each step.
-
Thus, T(n) is proportional to
. -
The time complexity is
.
Space Complexity
The space needed grows quickly because we store all the subsets.
- Recursive Call Stack:
- The deepest the recursion goes is n, but this is not the main use of space.
- Storage for All Subsets:
- Since there are
subsets, and each is stored in memory, the space required grows with .
- Since there are
- The space complexity is
.
Why Exponential Complexity Is Infeasible for Large Inputs
Exponential growth means that even a small rise in n causes a large increase in the number of subsets. For example:
- If n = 10, there are 2^10 = 1024 subsets.
- If n = 20, there are 2^20 = 1,048,576 subsets.
This quick rise makes the algorithm impractical for lists with many elements.
On this page
Key Characteristics
Code Example: Find All Subsets of a Given List
Complexity Analysis
Time Complexity
Space Complexity
Why Exponential Complexity Is Infeasible for Large Inputs